package com.limeng.datastruts.tree;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree {

    TreeNode root;

    public void insertNode(int data){
        root = insert(root,data);
    }

    private TreeNode insert(TreeNode node, int data){
        if(node==null) return new TreeNode(data);
        if (data<node.data){
            node.leftChild = insert(node.leftChild,data);
        }else if(data>node.data){
            node.rightChild = insert(node.rightChild,data);
        }else{
            node.data = data;
        }
        return node;
    }

    public void frontTravelr(TreeNode node){
        if(node==null) return;
        System.out.println(node.data);
        frontTravelr(node.leftChild);
        frontTravelr(node.rightChild);
    }

    public void midTravelr(TreeNode node){
        if(node==null) return;
        midTravelr(node.leftChild);
        System.out.println(node.data);
        midTravelr(node.rightChild);
    }

    public void levelTravelr(TreeNode node){
        if (node==null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            TreeNode n = queue.poll();
            System.out.println(n.data);
            if(n.leftChild!=null){
                queue.offer(n.leftChild);
            }
            if (n.rightChild!=null){
                queue.offer(n.rightChild);
            }
        }
    }


    public void afterTravelr(TreeNode node){
        if(node==null) return;
        afterTravelr(node.leftChild);
        afterTravelr(node.rightChild);
        System.out.println(node.data);
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insertNode(10);
        bst.insertNode(8);
        bst.insertNode(11);
        bst.insertNode(7);
        bst.insertNode(9);
        bst.insertNode(12);

        TreeNode root = bst.root;
        bst.frontTravelr(root);
        System.out.println("====================");
        bst.midTravelr(root);
        System.out.println("====================");
        bst.afterTravelr(root);
        System.out.println("====================");
        bst.levelTravelr(root);
    }

    class TreeNode{
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }
}
